COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂TO bmt@mit-mc 11:54 28-Oct-82
C00004 00003	Presentation to be given at IBM, 4-Nov-82
C00010 00004	Part II: Knowledge Acquisition
C00011 00005	Part III: Analogy
C00013 00006	Defn: from BGB & Duda82:
C00017 00007	(arbitrary) Task - PA to Yorktown Heights
C00019 00008	Consider first: Can I travel from my starting location, to my destination?
C00021 00009	Part II -- Knowledge Acquisition
C00022 00010	Presentation to be given at IBM, 4-Nov-82
C00028 ENDMK
C⊗;
∂TO bmt@mit-mc 11:54 28-Oct-82
[for Dr Griesmer:] Abstract
Presentation to be given at TJ Watson Research Center, IBM
4-Nov-82

Expert Systems, Knowledge Acquisition, and Analogy

This talk will describe various aspects of Expert Systems (ES).  The first
section is an introduction -- to characterize what an ES is, and, using  a
simple example,  to give a sense of how  an ES can operate.  This  section
concludes with a  brief discussion  on their  strengths and  deficiencies.
The second part  of this talk focuses on one major weakness:  the  primary
bottle-neck of ES design, Knowledge Acquisition.  After describing many of
the difficulties, I will outline  some of the current proposed  solutions.
The concluding  third  section sketches  my  preliminary thoughts  on  how
Analogy may be used during Knowledge Acquisition.

----
Dr Griesmer, Dr Hong, et al,

	I would appreciate hearing your comments on the implied talk,
especially if you feel it would be inappropriate for this visit, or
for this audience.
Also, am I correct in aiming for a one hour presentation?

Thank you,
	Russ

∂
Jim Griesmer called 2:43, 28-Oct-82, and spoke w/Jock
	Abstract is ok, talk = 1 hour, including questions
Presentation to be given at IBM, 4-Nov-82

Expert Systems, Knowledge Acquisition, and Analogy

Overhead
  [Selection of topic(s) - history]
	Several iterations to decide how not to say things I did not want to say.
	Had to abandon Ed's Rule for talks: [Never give talk for first time]
  Outline:
     [three interconnected areas]
	ES, concentrating on 
		[Why better than "hand coded procedure", "Baysean systems"]
	KA - difficulties, proposals
	Analogy - my approach
  Examples kept simple, to convey concepts.
	If they are familiar, please interrupt

-----
Part I: Expert Systems

A. Pep Talk/Overview
  0. Flavor of what ES is, and can do.
	Ask how other approaches would work - return @ Conclusion of this part.
  1. Ill defined
	a) my defn
	b) (from BGB & Duda82)
  2. Further Characterization
  3. List of Examples - diversity of domains
  4. Focus - rule based
	[not BB, or frame based, or ...]

B. Domain: Simplied Travel Agent
  0. Obvious domain, given hassles of getting here
	[cheaper to stay ... like:
	 "to England, via bombay" ... done by Winograd, Bobrow: GUS]
<Can say whether you can get there, but not how.>
  1. This not "expert"
	But shows features
  2. Types of facts
     [World facts, vs Control Facts]
	Base DB facts,
	Rules
	   Definitions, [e.g. CanReach]
	   Heuristics (e.g. nearest city [most are meta level:fewest stops, ...]
	Meta-Facts / Meta-Rules

C. Example Problem
  1. (arbitrary) Task - San Jose to NY
  2. [Here, given many flights, graphed out.]
<<<Describe goals, sub-goals, ... frontier>>>
  3. [Show back-chaining; using...]
  4. Comments
	(i) Note uniform system --
		Simple, declarative nature
	(ii) This made system 
		easy to understand,
		simple to modify, extend, debug
	(iii) [below] System can be
		adapted to other extensions/applications

D. Next - more complexities:
  0. To tell which flights, record [by Concatenating]
  1. Change CanReach's "defn"
	a) include Bus from SJ to SF
	b) Extend to: PA to Yorktown Heights
		Heuristic: Find close by major city [and, if > 1, ...]
  2. Can add further constraints, to change behavior
+** Given Conflict Resolution Strategy: find first ***
     [needs additional facts - Knowledge is Power]
	most convenient [= most flights], so use Big airlines: United, ...
	fastest, [those w/most fast planes, fewest stops, ...]
	cheapest, [e.g. Try World, PeopleExpress first]
<<<HeadQuarter for Delta is Dallas, so try them first.>>>

     NOTE: did NOT change inference engine - still general PC unify/resolution ...
  3. Meta Level assertions -
	Direction of search, based on "chuminess of city"
	  [Here, for efficiency. Other times, to avoid infinite loops, or ...]
	[Still same "resolution", enhanced to consider meta level ...]

E. Conclusion
  1. Showed simple system, easy to change
	- both inferences, goals, efficiency
  2. Recall challenge - how to make these changes with other types of systems.
  3. What of Explanation
    (i)	This example trivial -- few rules, too shallow, not interactive
	(Still could say why not this route, or ..., pointing to rule.  
	+ can answer why it found this flight 
	  i.e. what assumptions it made, as explicit
    (ii) Scale up - show Mycin example - real rules.
	[Show how explanation "fall out"]
  4. mycin points out difficulty of enterring KB,
	input is really vague, and heuristic...
	Leads to KA...

------
Part II: Knowledge Acquisition

A. Def'n of KA

B. Problem
  0. At each section

C. Proposed solutions
  0. To each case in turn

Common sense facts
World complex
Those who can, do; those who can't, teach.
Part III: Analogy

[back up, to discuss analogy. Then back to solving this problem]

A. Two areas of Research
  1. Adequate def'n of Analogy
	As in "What's in an Analogy" (w/MRB)
  2. Running System, 
	Using formalism
  3. Discuss latter

B. Def'n of my task:
  1. Use of Analogy for KA - not Problem Solving, ...
  2. Why chosen? - well constrained, ...

C. Example 1
  0. Simple -- "automated copy & edit"
  1. "VM is like BM, except ..."
  2. Context
  3. Sample Rules, facts, ...
  4. Desired conclusions

D. Example 2
  0. More elaborate
  1. "Renal system is like Electrical System, in that both are circuits"
...

E. Research methodology, time table, ...

------
Final comments:
  Credit: MRG and DBL all around; and to TGD & JSB for KA


Questions?
Defn: from BGB & Duda82:
A computer Program that provides expert-level solutions to important problems
and is:
Heuristic: reasons w/judgement knowledge as well as formal knowledge
Transparent: probides explanations of its line of reasoning and answers
	queries about is knowledge
Flexible: integrates new knowledge incrementally.

General Character:
Often deals will difficult problems,
Usually w/uncertain, or errorful, data

Refinement:
[like that article, we'll focus on Rule Based systems.]


-----
Comparison with 
	(i) Simple Procedures
	(ii) Baysean Systems

[Will describe single example - which pins down some aspects.
 Still true elsewhere, for BBs, or Frame Based Systems, ...]

Inference scheme is simple, "driven" by the facts

Facts are MODULAR - making the system
	quick to build
	easy to (debug) modify
	explanatory (i.e. it can explain its conclusions)

Declarative - so facts can be used for other purposes.

Back-chaining -
	So can be "Hierarchical" -- can narrow down conclusions...
	Meta - is easy, can even use same inference...

Ex: Mycin
	(or Kinship, or Symbolic Integration [NO:  their field], or
	 Circuit Diagnosis [NO: DART], ...)
(arbitrary) Task - PA to Yorktown Heights

Find flight ?F s.t.
	(Flight ?F PA YorktownHeights)

Static, Domain level Facts

(Flight	American#28 SJC Chicago)
(Airline American#28 American)
; No - really for both flights!! (Cost	American#28 $109)
(Periodicity American#28 Daily)
(Times American#28 9:28AM 3:15PM)

(Flight	American#446 SJC Leguardia)
(Airline American#446 American)
(Periodicity American#446 Daily)
(Times American#446 4:00PM 6:59PM)


***** NY→WPB *****
 5/XI	Eastern #883	NY-Leg	WPB		[$129]
Fri			2:20PM	4:55PM

***** WPB→Boston *****
 8/XI	Eastern #1608	WPB	Atlanta		[$99]
Mon			9:35AM	11:04AM
	Eastern #690	Atlanta	Boston
			12:23PM	2:40PM

***** Boston→SJ *****
10/XI	American #315	Boston	Dallas		[$169]	<15D>
Wed			5:46PM	8:50PM
	American #507	Dallas	SJC			<15D>
			9:35PM	11:02PM

-----
$754 for
	SJC →  NY on 3/XI,
	NY  → SJC on 5/XI
(Flight American
Consider first: Can I travel from my starting location, to my destination?
[later issues of what is that path,
and then more complex]

Rules:

Base-CanReach:
∀ $From, $To, $F. (Flight $F $From $To)  => (CanReach $From $To)

Transitivity-CanReach:
∀ A, B, C. (CanReach A B) & (CanReach B C) => (CanReach A C)

[could use 2nd order Transitive(CanReach)]

-----

MetaRules:

IF ( (TryingToAchieve (CanReach $A $B)) & (LightlyTravelled $A) )
 THEN "SubGoal from departure point, $A"

[i.e. find those (CanReach $A <to>) first,
 (using (Flight <f1> $A <to>) )
 then worry about (CanReach <to> $B). ]
That is, use
Transitivity-CanReach-1 rather than Transitivity-CanReach, where
Transitivity-CanReach-1:

∀ F, A, B, C. (Flight F A B) & (CanReach B C) => (CanReach A C)
-----
Reciprically,

IF ( (TryingToAchieve (CanReach $A $B)) & (LightlyTravelled $B) )
 THEN "SubGoal from destination, $B"

That is, use
Transitivity-CanReach-2 rather than Transitivity-CanReach, where
Transitivity-CanReach-2:

∀ F, A, B, C. (CanReach A B) & (Flight F B C) => (CanReach A C)

Part II -- Knowledge Acquisition

This is main bottleneck.
Why?  (present here several possibilities - credit to Tom D and Jim B)

... Experts have not explicated facts (why else apprentiseship)
Usually work by examplars, not rules (or other hard causal...)
Much "compiled in" - like driving a car

....

Part III -- Analogy
Corollary: Analogy will help.
First, consider what I mean here by analogy:
	not as reasoning, per se, but as way of inputting "data"
Presentation to be given at IBM, 4-Nov-82

*** OverView of Analogy ***

Outline

Intro/Motivation
   [Why analogy] Analogies used all the time
   [Why paper] No one has formalized what is going on
   [What is paper] NOT: how description of how to use an analogy;
	rather, what it means to use an analogy ...
	is a formalizaion of what it is -- i.e. not code, ...
   [Outline of talk] 
   [Meta Note] Represents research in progress. 
	∃ still many unanswered questions -- this just provides some of
	vocabulary needed to address them.
*** this is important, to keep audience interested ***

Framework of an analogy?
  From facts, assert Analogous(A B ...)
  From Analogous(A B...), and F1(A B), deduce some F2(A B)
  Ex:	VM like BM => VM is a disease,
	EC like Water Flow => Expect some resouviour -- battery, (or do diagnosis...)
  [Specific subcases:
	Using f1(B), deduce f1'(A), where f1 and f1' are related.
	Usually weakened to *Conjecture* new proposals ... ]

  Now consider what goes into these Analogous propositions:

>2 args
   At least 2 - the analogues
	[in what form? We'll disuss later]
   [Case for exactly 2 args]
	Std usage
	Winston, Carbonell, ... 
   Ex: Fred & George; Washington:1::Lincoln:?; ...
   Must be something else - the context, or "answer" (mapping, theory, ...), ...

Two digression here:
   (Surface) Linguistic?, or deep
   Why is binary Analogous so seductive?

(before asking for other args,)
What are "analogue args"?
   [Other args are function of this -- e.g. mapping over SOMETHING]
   Cannot be objects themselves, ... rather ... a description of it
   --- leads to reformulation

(1) Analogy = Common Theory
   3 arg = that theory, which each analogue instantiates
   Ex: Biological tree and corporate hierarchy  -- each is a tree (in CS sense)
	or Renal system & Electrical System -- each is a circuit, ...
   Useful for
	1. extracting relevant features of A and B 
	   (and ok at putting parts into correspondence)
	2. establishing new facts about "new" analogue (in canonical use)
	   Ex: diagnosis for RS, based on ES
	3. can compile inventory - so given A and B can find common C readily
	4. Combining analogies, to ...
	<others, pertaining to analogy qua object for study - comparison, ...>
   Problems
	1. No explicit mapping, of differences
	   Ex: "after substituting..." or ...
	2. ...

(2) Analogy = Mapping
   3rd arg = mapping function.
   Ex: shakespeare plays, ...
   Useful for
	1. explicating differences
   Problems
	1. explicating commonalities
	2. building inventory

----
Solution - elements of both
	[See Polya - sibling of "generalization" hierarchy]
  Explicate both commonality and differences

Remaining issues
  *** here gets fuzzier ***
   Symbol-symbol mapping inappropriate - need sentence to sentence
	now need to constrain this -- i.e. recursive...
   Reformulation -- the initial represention of the analogue(s) may not
	explicate the connection -- may need to find some other description
	[e.g. circle : sphere obvious in polar coordiates [r=constant, others
	 arbitrary], but hard in rectangular... See polya for class of problems]
	Learn that wire go both ways, as conduits in the body do -- and so an "input"
	 to a circuit could drive something else to zero.

-----
My work-
	Use of analogy for KA
...

---
Reformulation